package com.txy.strmatch;

/**
 * 滑动 时间复杂度O(n/m)
 */
public class BM {
    private static void genBC(char[] b, int m, int[] dc) {
        // 初始化字段
        for(int i=0;i<256;i++) {
            dc[i] = -1;
        }
        // 将模式串中的坏字符写入字典
        for(int i=0;i<m;i++) {
            int asc = (int)b[i];
            dc[asc] = i;
        }

    }

    public static int bad(char[] main, char[] pattern) {
        int n = main.length;
        int m = pattern.length;
        int[] bc = new int[256];
        genBC(pattern, m, bc);

        int i = 0;
        while(i<=n-m) {
            int j;
            for(j=m-1;j>=0;j--) {
                if(main[i+j]!=pattern[j]) {
                    break;
                }
            }
            if(j<0) {//匹配成功
                return i;
            }
            // 没匹配上，滑动si-xi
            i = i + (j - bc[(int)main[i+j]]);
        }
        return -1;
    }

    public static void main(String[] args) {
        String s1 = "abcabcabc";
        String s2 = "cab";
        System.out.println(bad(s1.toCharArray(), s2.toCharArray()));
    }
}
